package q2251_fullBloomFlowers;

import java.util.Arrays;
import java.util.HashMap;
import java.util.stream.IntStream;

public class Solution_1 {
    /*
    花期内花的数目
    差分法
     */
    public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        var diff = new HashMap<Integer, Integer>();
        for (var f : flowers) {
            diff.put(f[0], diff.getOrDefault(f[0], 0) + 1);
            diff.put(f[1] + 1, diff.getOrDefault(f[1] + 1, 0) - 1);
        }
        var times = diff.keySet().stream().mapToInt(Integer::intValue).sorted().toArray();

        var n = persons.length;
        var ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(ids, (i, j) -> persons[i] - persons[j]);

        var ans = new int[n];
        int i = 0, sum = 0;
        for (var id : ids) {
            while (i < times.length && times[i] <= persons[id])
                sum += diff.get(times[i++]); // 累加变化量
            ans[id] = sum;
        }
        return ans;
    }
}
